package com.heima.datastructure.heap;

import java.util.Iterator;

/**
 * <strong>大顶堆</strong>
 * <ul>
 *     <li>建堆
 *         <ul>
 *             <li>方法一：威廉姆斯法
 *                <ol>
 *                    <li>遍历提供的数组，一个一个加到堆中</li>
 *                    <li>然后与父节点比较把新加入的元素上潜到合适的位置</li>
 *                    <li>假设数据规模为n，那么一共要上潜n次，一次上潜的时间复杂度为log(n)</li>
 *                    <li>时间复杂度为O(nlog(n))</li>
 *                </ol>
 *            </li>
 *            <li>方法二：弗洛伊德法
 *                <ol>
 *                    <li>将提供的数组直接赋值给堆里面包装的数组</li>
 *                    <li>找到最后一个有叶子节点的节点</li>
 *                    <li>将其下潜到合适的位置</li>
 *                    <li>然后往前遍历，把遍历到的节点下潜到合适位置</li>
 *                    <li>直到根节点下潜到指定位置</li>
 *                    <li>假设数据规模为n，完全二叉树的高度为H（从1计数），假定当前层的高度为h，那么当前层的层数是(H - h)（从0计数）
 *                        <ol>
 *                            <li>h = 1的节点：最多下潜0次，高度h = 1的这一层最多下潜2^(H - 1) * 0次</li>
 *                            <li>h = 2的节点：最多下潜1次，高度h = 2的这一层最多下潜2^(H - 2) * 1次</li>
 *                            <li>h = 3的节点：最多下潜2次，高度h = 3的这一层最多下潜2^(H - 3) * 2次</li>
 *                            <li>h = 4的节点：最多下潜3次，高度h = 4的这一层最多下潜2^(H - 4) * 3次</li>
 *                            <li>……</li>
 *                            <li>h = H的节点：最多下潜H - 1次，高度h = H的这一层最多下潜2^(H - H) * (H - 1)次</li>
 *                            <li>所以求和2^(H - 1) * 0 + 2^(H - 2) * 1 + …… + 2^(H - H) * (H - 1) = -H + 2^H - 1</li>
 *                            <li>数据规模n = 2^(H - H) + 2^1 + 2^2 + …… + 2^(H - 1) = 2^H - 1</li>
 *                            <li>所以时间复杂度为O(n)</li>
 *                        </ol>
 *                    </li>
 *                    <li>时间复杂度为O(n)</li>
 *                </ol>
 *            </li>
 *         </ul>
 *     </li>
 * </ul>
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/5 17:13
 */
public class MaxHeap<E extends Value> implements Heap<E>, Iterable<Integer> {
    // Value是上界，如果指定泛型E为数组元素的类型会有问题，
    // E[] arr = 开辟元素类型为Value的数组空间吧，肯定不够存实现类的其他扩展功能，
    // E[] arr = 开辟元素类型为Object的数组空间吧，又会因为超出上界Value报错
    // 这里选择创建以父类或者接口为数组元素类型的数组，开辟元素类型为Value的数组空间
    // 然后通过多态，数组中每个Value类型的元素引用的是实现类的实例
    // E需要指定后是唯一的一个类，那么存的时候和取的时候类型转换：子类转父类，父类转自类就不会有问题
    // 父类转子类或者说接口转实现类会出现的问题：
    // 1、存的时候存入了多种子类型，取的时候不知道该怎么转换，
    // 2、存的时候存的就是一个父类，取的时候就不能转成一个子类，因为子类的扩展方法该如何来？难道天上来？
    private Value[] arr; // 数组，
    private int size; // 堆的大小

    /**
     * 用构造器初始化
     *
     * @param capacity 数组容量
     */
    public MaxHeap(int capacity) {
        arr = new Value[capacity];
    }

    /**
     * 用有参构造快速创建一个堆
     *
     * @param arr 数组
     */
    public MaxHeap(E[] arr) {
        this.arr = arr;
        size = arr.length;
        heapify();
    }

    /**
     * 建堆，将一般的数组转化为堆，弗洛伊德算法，时间复杂度O(n)
     */
    @Override
    public void heapify() {
        // 找到最后一个有叶子节点的节点或者说找到最后一个非叶子节点
        // 等同于找到最后一个叶子节点的父节点：(size - 1 - 1) / 2 => size / 2 - 1
        // 然后往前遍历，让遍历到的元素下潜到合适的位置
        for (int index = (size >> 1) - 1; index >= 0; index--) {
            down(index);
        }
    }

    /**
     * 往堆尾部新增元素
     *
     * @param value 新增元素
     * @return 是否新增成功
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        up(value); // 多态的传入参数
        size++;
        return true;
    }

    /**
     * 获取堆顶元素并删除，然后重构
     *
     * @return 堆顶元素
     */
    @SuppressWarnings("all")
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        swap(0, --size);
        E value = (E) arr[size];
        arr[size] = null;
        down(0);
        return value;
    }

    /**
     * 获取指定索引处的元素并删除，然后重构
     *
     * @param index 索引
     * @return 指定索引处的元素
     */
    @SuppressWarnings("all")
    @Override
    public E poll(int index) {
        if (index >= size || index < 0) {
            throw new IllegalArgumentException("索引 " + index + " 不合法");
        }
        E value = (E) arr[index];
        size--;
        if (index != size) { // 删除最后一个节点，自己和自己交换并且删除后arr[index]是空指针
            swap(size, index);
            int parent = (index - 1) / 2;
            if (index == 0 || arr[parent].getValue() > arr[index].getValue()) { // 根节点没有父节点，parent指针会乱指
                down(index);
            } else if (arr[parent].getValue() < arr[index].getValue()) {
                up(index);
            }
        }
        arr[size] = null;
        return value;
    }

    /**
     * 获取堆顶元素
     *
     * @return 堆顶元素
     */
    @SuppressWarnings("all")
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) arr[0];
    }

    /**
     * 获取指定索引处的元素
     *
     * @param index 索引
     * @return 指定索引处的元素
     */
    @SuppressWarnings("all")
    @Override
    public E peek(int index) {
        if (index >= size || index < 0) {
            throw new IllegalArgumentException("索引 " + index + " 不合法");
        }
        return (E) arr[index];
    }

    /**
     * 替换堆顶元素
     *
     * @param value 新堆顶元素
     */
    @Override
    public void replace(E value) {
        if (isEmpty()) {
            throw new IllegalArgumentException("堆为空，堆顶元素不存在");
        }
        arr[0] = value;
        down(0);
    }

    /**
     * 判断堆是否为空
     *
     * @return 为空返回true
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 判断堆是否为满
     *
     * @return 为满返回true
     */
    @Override
    public boolean isFull() {
        return size == arr.length;
    }

    /**
     * 获取堆的大小
     * @return 大小
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 扩容
     *
     * @param capacity 扩展到多少容量
     */
    @Override
    public void expansion(int capacity) {
        if (capacity <= arr.length) {
            throw new IllegalArgumentException("参数 <" + capacity + "> 不能比" + arr.length + "小");
        }
        Value[] array = new Value[capacity];
        System.arraycopy(arr, 0, array, 0, size);
        arr = array;
    }

    /**
     * 迭代器
     *
     * @return 迭代器，迭代时取出value
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {
            int index = 0;

            @Override
            public boolean hasNext() {
                return index != size;
            }

            @Override
            public Integer next() {
                return arr[index++].getValue();
            }
        };
    }

    /**
     * 重写toString方法只输出堆里存的value，按照层序遍历的方式输出
     *
     * @return 转成的字符串
     */
    @Override
    public String toString() {
        int prevLevelsSize = 0; // 当前前面层的节点总数
        int currentLevel = 0; // 当前层，从0计数
        StringBuilder builder = new StringBuilder(size);
        builder.append("[");
        for (int i = 0; i < size; i++) {
            // 先加入遍历到的元素
            builder.append(arr[i].getValue());
            // 处理到了一层的最后一个节点
            if (power(2, currentLevel) + prevLevelsSize == i + 1) {
                prevLevelsSize = i + 1;
                builder.append("]");
                builder.append("\r\n");
                builder.append("[");
                currentLevel++;
            } else if (i + 1 == size) {
                break;
            } else {
                builder.append(" ");
            }
        }
        builder.append("]");
        return builder.toString();
    }

    /**
     * 指定索引位置的元素下潜
     *
     * @param parent 指定节点索引
     */
    private void down(int parent) {
        int leftChild = parent * 2 + 1;
        int rightChild = leftChild + 1;
        // 递的时候找到父节点、左子节点、右子节点中求出value最大的节点
        int max = maxValue(parent, leftChild, rightChild);
        // 如果是父节点，那就是不用下潜了，就是终止条件
        if (max == parent) {
            return;
        }
        // 如果是左子节点，需要父节点与左子节点交换
        // 如果是右子节点，需要父节点与右子节点交换
        // max既可以表示左子节点也可以表示右子节点
        swap(parent, max);
        down(max);
        // 归的时候啥也不干
    }

    /**
     * 将元素上潜到合适的位置再插入
     *
     * @param value 指定索引的元素
     * @param index 指定索引处上潜
     */
    private void up(Value value, int index) {
        int child = index;
        int parent = (child - 1) / 2;
        while (child > 0 && arr[parent].getValue() < value.getValue()) { // 根节点没有父节点，value相等不用交换，提升性能
            swap(parent, child);
            child = parent;
            parent = (child - 1) / 2;
        }
        arr[child] = value;
    }

    /**
     * 默认是向堆尾插入一个元素然后上潜到合适位置
     *
     * @param value 元素
     */
    private void up(Value value) {
        up(value, size);
    }

    /**
     * 将指定索引处的元素上潜到合适的位置
     *
     * @param child 索引
     */
    private void up(int child) {
        up(arr[child], child);
    }

    /**
     * 找出父节点，左子节点，右子节点中value最大的节点
     *
     * @param parent     父节点
     * @param leftChild  左子节点
     * @param rightChild 右子节点
     * @return value最大的节点在数组中的索引
     */
    private int maxValue(int parent, int leftChild, int rightChild) {
        if (leftChild >= size) {
            return parent;
        }
        if (rightChild == size) {
            return arr[parent].getValue() >= arr[leftChild].getValue() ? parent : leftChild;
        }
        if (arr[parent].getValue() >= arr[leftChild].getValue()) { // 父节点等于左子节点并且大于右子节点时就应该返回parent，减少交换次数
            return arr[parent].getValue() >= arr[rightChild].getValue() ? parent : rightChild; // 同样父节点大于等于左子节点后如果还等于右子节点，那么应该返回parent，减少交换次数
        }
        return arr[leftChild].getValue() >= arr[rightChild].getValue() ? leftChild : rightChild; // 这里是左子节点大于或等于右子节点时，返回左子节点
    }

    /**
     * 交换两个索引位置的节点
     *
     * @param index1 索引一
     * @param index2 索引二
     */
    private void swap(int index1, int index2) {
        Value temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    /**
     * 计算次幂式子
     *
     * @param base     底数
     * @param exponent 幂
     * @return 运算结果
     */
    private int power(int base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (base == 2) {
            return 1 << exponent;
        }
        return base * power(base, exponent - 1);
    }
}
